/**
 * @author: tengjuyuan
 * @file: List.h
 * 链表的模拟实现
 */
#pragma once
#include <iostream>
using namespace std;

template <typename Object>
class List
{
private:
    struct Node;
public:
    class const_iterator;
    class iterator;

public:
    List();
    List(const List& list);
    const List& operator=(const List& rhs);
    ~List();

    iterator begin()
    {
        return iterator(head->next);
    }
    const_iterator begin() const
    {
        return const_iterator(head->next);
    }
    iterator end()
    {
        return iterator(tail);
    }
    const_iterator end() const
    {
        return const_iterator(tail);
    }

    int size() const
    {
        return theSize;
    }
    bool empty() const
    {
        return size() == 0;
    }

    void clear()
    {
        while(!empty())
            pop_front();
    }

    Object& front()
    { return *begin(); }
    const Object & front() const
    { return *begin(); }
    Object& back()
    { return *--end(); }
    const Object & back() const
    { return *--end(); }

    void push_front(const Object & x)
    { 
        insert(begin(), x); 
    }
    void push_back(const Object & x)
    { 
        insert( end(), x); 
    }
    void pop_front()
    { 
        erase( begin() ); 
    }
    void pop_back()
    { 
        erase( --end() );
    }

    iterator insert(iterator itr, const Object & x);
    iterator erase(iterator itr);
    iterator erase(iterator start, iterator end);

private:
    int theSize;
    Node* head;
    Node* tail;

    void init();
};

// 这里是数据结构体
template <typename Object>
struct List<Object>::Node
{
    Object data;
    struct Node* prev;
    struct Node* next;
    Node(const Object& d = Object(), Node* p = NULL, Node* n = NULL)
     : data(d)
     , prev(p)
     , next(n)
     {
     }
};


template <typename Object>
class List<Object>::const_iterator
{
public: 
    typedef typename List<Object>::Node _Node;
    const_iterator() : current(NULL)
    { }

    const Object & operator* () const
    { return retrieve(); } 

    // 前置++
    const_iterator & operator++()
    {
        current = current->next;
        return *this;
    }

    // 后置++
    const_iterator operator++(int)
    {
        const_iterator old = *this;
        ++(*this);
        return old;
    }

    bool operator== (const const_iterator & rhs)
    { return current == rhs.current; }
    bool operator!= (const const_iterator & rhs)
    { return !(*this == rhs); }
public:
    _Node* current;

    Object & retrieve() const
    { return current->data; }

    const_iterator(_Node *p) : current(p)
    { }
    
    friend class List<Object>;
};

template <typename Object>
class List<Object>::iterator : public List<Object>::const_iterator
{
public:
    typedef typename List<Object>::Node _Node;
    iterator()
    { }

    Object & operator* ()
    { return this->retrieve(); }

    const Object & operator*() const
    {
        return const_iterator::operator*();
    }

    // 前置++
    iterator & operator++ ()
    {
        this->current = this->current->next;
        return *this;
    }

    // 前置--
    iterator & operator-- ()
    {
        this->current = this->current->prev;
        return *this;
    }

    iterator operator++(int)
    {
        iterator old = *this;
        ++(*this);
        return old;
    }
protected:
    iterator(_Node *p) : const_iterator(p)
    { 
        //cout << "current " << this->current << endl;
    }
    friend class List<Object>;
};

template <typename Object>
List<Object>::List()
{
    init();
}

template <typename Object>
List<Object>::~List()
{
    clear();
    delete head;
    delete tail;
}

template <typename Object>
List<Object>::List(const List& rhs)
{
    init();
    *this = rhs;
}

template <typename Object>
const List<Object> & List<Object>::operator= (const List &rhs)
{
    if (this == &rhs)
    {
        return *this;
    }
    clear();
    for(const_iterator itr = rhs.begin();
        itr != rhs.end();
        ++itr)
    {
        push_pack(*itr);
    }
    return *this;
}

template <typename Object>
void List<Object>::init()
{
    theSize = 0;
    head = new Node;
    tail = new Node;
    head->next = tail;
    tail->prev = head;
}

template <typename Object>
typename List<Object>::iterator 
List<Object>::insert(List<Object>::iterator itr, const Object & x)
{
    List<Object>::Node* p = itr.current;
    theSize++;
    
    // List<Object>::Node* newNode = new List<Object>::Node(x, p->prev, p);
    // p->prev->next = newNode;
    // p->prev = newNode;
    return List<Object>::iterator(p->prev = p->prev->next = new List<Object>::Node(x, p->prev, p));
}

template <typename Object>
typename List<Object>::iterator 
List<Object>::erase(List<Object>::iterator itr)
{
    List<Object>::Node* p = itr.current;
    List<Object>::iterator retVal(p->next);
    p->prev->next = p->next;
    p->next->prev = p->prev;
    delete p;
    theSize--;
    return retVal;
}

template <typename Object>
typename List<Object>::iterator 
List<Object>::erase(List<Object>::iterator start, List<Object>::iterator end)
{
    for (List<Object>::iterator itr = start; itr < end; )
    {
        itr = List<Object>::erase(itr);
    }

    return end;
}
